#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    // 请在此输入您的代码
    int N;
    cin >> N;
    vector<int> arr(N + 1);
    for (int i = 1;i <= N;i++)
    {
        cin >> arr[i];
    }

    /*vector<int> low(2);
    low[1] = arr[1];
    for (int i = 2;i <= N;i++)
    {
        if (arr[i] > low[low.size() - 1])
        {
            low.push_back(arr[i]);
        }
        else
        {
            int index = upper_bound(low.begin() + 1, low.end(), arr[i]) - low.begin();
            low[index] = arr[i];
        }
    }
    cout << low.size() - 1 << endl;
    return 0;*/

    //若提前分配好空间大小，low(N+1)，后面再用一个length记录数据长度，代码实际上会更简洁 
    vector<int> low(N + 1);
    int length = 1;
    low[1] = arr[1];
    for (int i = 2;i <= N;i++)
    {
        if (arr[i] > low[length]) low[++length] = arr[i];
        else
        {
            int index = upper_bound(low.begin() + 1, low.begin() + 1 + length, arr[i]) - low.begin();
            low[index] = arr[i];
        }
    }
    cout << length;
    return 0;
}